﻿using System;
using System.Text;
using System.Collections.Generic;

namespace DNA
{
    static class DnaProcessor
    {
        public static string ReverseString(string nucl)
        {
            StringBuilder _builder = new StringBuilder();
            _builder.Remove(0, _builder.Length);
            _builder.EnsureCapacity(nucl.Length);
            int x = nucl.Length;
            for (int i = 0; i < nucl.Length; i++)
            {
                char c = nucl[--x];
                _builder.Insert(i, c);
            }

            return _builder.ToString();
        }

        public static List<string> Merge(List<string> list)
        {
            DnaIndex index = new DnaIndex(list);
            DnaIndexReversed revIdx = new DnaIndexReversed(index);
            List<string> used = new List<string>();
            Dictionary<string, int> dict = new Dictionary<string, int>();

            List<string> unused = index.getAll();

            while (unused.Count != 0)
            {
                string current = unused[0];
                unused.Remove(current);
                index.Remove(current);
                revIdx.Remove(current);

                int i;
                if (!dict.ContainsKey(current))
                    dict[current] = 1;
                
                i = dict[current];


                string suffix = current.Substring(i);
                string prefix = current.Substring(0, current.Length - i);

                List<string> suffixes = index.findAllStartingWith(suffix);
                List<string> prefixes = revIdx.findAllEndingWith(prefix);

                int suffCnt = suffixes.Count;
                int prefCnt = prefixes.Count;

                if (suffCnt == 1)
                {
                    string next = suffixes[0];
                    if (!dict.ContainsKey(next))
                        dict.Add(next, 1);

                    unused.Remove(next);
                    index.Remove(next);
                    revIdx.Remove(next);

                    int x = dict[current];
                    int y = dict[next];

                    current = current + next.Substring(suffix.Length);
                    if (!dict.ContainsKey(current))
                        dict.Add(current, x+y);
                    else
                        dict[current] = x+y;
                    /*Console.WriteLine(">" + current + "<>" + next);
                    Console.ReadKey();*/
                }

                if (prefCnt == 1)
                {
                    string prev = prefixes[0];
                    if (!dict.ContainsKey(prev))
                        dict.Add(prev, 1);

                    unused.Remove(prev);
                    index.Remove(prev);
                    revIdx.Remove(prev);

                    int x = dict[current];
                    int y = dict[prev];

                    current = prev + current.Substring(prefix.Length);
                    if (!dict.ContainsKey(current))
                        dict.Add(current, x+y);
                    else
                        dict[current] = x+y;
                }

                if (prefCnt == 1 || suffCnt == 1)
                {
                    unused.Add(current);
                    index.Add(current);
                    revIdx.Add(current);
                }
                else
                {
                    //Console.WriteLine(">>>"+current);
                    used.Add(current);
                }
            }

            /*Console.WriteLine("[][][][][][][][][][][][][][][]");
            foreach (var str in used)
            {
                Console.WriteLine(str + "\t" + dict[str]);
            }
            Console.WriteLine("[][][][][][][][][][][][][][][]");*/

            return used;            
        }

        public static void test(string A, string B)
        {
            string newA;
            string newB;
            Console.WriteLine("Testing Alignment");
            Console.WriteLine("-----------------");            
            int result = Align(A, B, out newA, out newB);            
            Console.WriteLine("Compared strings:");
            Console.WriteLine(A);
            Console.WriteLine(B);
            Console.WriteLine("\n quality od alignment: {0}", result);
            Console.WriteLine("\n Aligned Strings");
            Console.WriteLine(newA);
            Console.WriteLine(newB);
            Console.WriteLine("-----------------");
        }


        public static int Align(string A, string B, out string newA, out string newB)
        {
            bool verbose = true;
            /************** parameters *******************************/
            int gap = -6;                             //gap penalty
            int match = 1;                            //mach score
            int misMatch = -1;                        //mismatch penalty
            /**********************************************************/
            
            int[,] S = new int[A.Length + 1, B.Length + 1];         //Score array
            char[,] T = new char[A.Length + 1, B.Length + 1];       //Traceback array
            newA = new String(' ', 0);                              //output string initialization
            newB = new String(' ', 0);

            int i, j;
            int score = 0;

            /*******Score and traceback array initialization**********/
            for (i = 0; i <= A.Length; i++)                  
            {
                S[i, 0] = i * gap;
                T[i, 0] = 'l';
            }

            for (i = 0; i <= B.Length; i++)
            {
                S[0, i] = i * gap;
                T[0, i] = 'u';
            }
            /************************************************************/

            /****************Filling score and traceback arrays**********/
            for (i = 1; i <= A.Length; i++)
                for (j = 1; j <= B.Length; j++)
                {
                    if (A[i-1] == B[j-1]) 
                        score = match;
                    else
                        score = misMatch;

                    int m = S[i-1, j-1] + score;        //don't intorduce gap
                    int gA = S[i-1, j] + gap;           //introduce gap in A
                    int gB = S[i, j-1] + gap;           //introduce gap in B

                    int max = Math.Max(m, Math.Max(gA, gB));
                    
                    S[i,j] = max;                        
                    
                    if(gA == max)
                        T[i, j] = 'l';
                    if(gB == max)
                        T[i, j] = 'u';
                    if (m == max)
                        T[i, j] = 'd';
                }
            /*************************************************************/

            /****************printing score and traceback arrays**********/
            if (verbose)
            {
                for (j = 0; j <= B.Length; j++)
                {
                    Console.Write("\n");
                    for (i = 0; i <= A.Length; i++)
                    {
                        Console.Write("{0}\t", S[i, j]);
                    }
                }
                Console.Write("\n");

                for (j = 0; j <= B.Length; j++)
                {
                    Console.Write("\n");
                    for (i = 0; i <= A.Length; i++)
                    {
                        Console.Write("{0} ", T[i, j]);
                    }
                }
                Console.Write("\n\n");
            }
            /***************************************************************/
            
            
            /*******Reconstructing optimal solution from traceback array*****/
            i = A.Length;
            j = B.Length;
            int k = 0;
            int result = 0;
            
            while ((i != 0) || (j != 0))
            {
                if (T[i, j] == 'u')                         //introduce a gap in A. Move up in arrays
                {
                    newA = newA.Insert(k, "_");
                    newB = newB.Insert(k, B.Substring(j-1, 1));
                    result += S[i, j];
                    j--;
                    k++;                    
                }
                else if (T[i, j] == 'l')                //introduce gap in B. Move left in arrays
                {
                    newA = newA.Insert(k, A.Substring(i - 1, 1));
                    newB = newB.Insert(k, "_");
                    result += S[i, j];
                    i--;
                    k++;
                }
                else if (T[i, j] == 'd')                //Rewrite characters in both strings. Move diagonaly
                {
                    newA = newA.Insert(k, A.Substring(i-1, 1));
                    newB = newB.Insert(k, B.Substring(j-1, 1));
                    result += S[i, j];
                    i--;
                    j--;
                    k++;

                }
            }
            /*************************************************************/

            /***Strings have to be revesed because we constructed solution from the end***/
            newA = ReverseString(newA);
            newB = ReverseString(newB);
            

            return result;
        }

    }

}
